package edu.hunau.cxb19.basic.class09;

import java.util.Arrays;

/**
 *
 * @author hb
 *
 *         2020-02-19 14:58:43
 */
public class SortDemo {
	public static void main(String[] args) {
		int[] arr = { 24, 45, 6, 68, 3, 23, 34,1 };
		Arrays.sort(arr);
		System.out.println(Arrays.toString(arr));
		
		
		
		System.out.println("插入排序");
		/*
		 * insertSort02(arr); print(arr);
		 */
	}

	public static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	public static void insertSort02(int[] arr) {
		// i表示第二部分的第一个数据的位置
		for (int i = 1; i < arr.length; i++) {
			int temp = arr[i];// 使用临时变量，存储第2部分的第一个数据
			// 使用j表示第1部分的数据的下标
			if (arr[i] < arr[i - 1]) {
				int j = i - 1;
				for (; j >= 0 && arr[j]>temp; j--) {
						arr[j + 1] = arr[j];
				}
				arr[j + 1] = temp;
			}
		}

	}

	public static void insertSort(int[] arr) {
		// i表示第二部分的第一个数据的位置
		for (int i = 1; i < arr.length; i++) {
			int temp = arr[i];// 使用临时变量，存储第2部分的第一个数据
			// 使用j表示第1部分的数据的下标
			int j = i - 1;
			for (; j >= 0; j--) {
				if (arr[j] > temp) {// 符合条件
					// 当前的arr[j]的数据应该向后移动一位
					arr[j + 1] = arr[j];
				} else {
					break;
				}
			}
			arr[j + 1] = temp;
		}

	}

	/**
	 * 采用冒泡排序
	 * 
	 * @param arr
	 */
	public static void bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {// i表示当前的轮次
			// j表示两个相邻数据的下标
			for (int j = 0; j < arr.length - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					// 升序：前面大于后面的数据，进行交换
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
	}

	/**
	 * 采用冒泡排序
	 * 
	 * @param arr
	 */
	public static void bubbleSort02(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {// i表示当前的轮次
			boolean flag = false;
			// j表示两个相邻数据的下标
			for (int j = 0; j < arr.length - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					// 升序：前面大于后面的数据，进行交换
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;

					flag = true;
				}
			}
			// 如果没有发生数据的移动，说明当前的序列是有序的序列。
			if (!flag) {
				break;
			}
		}
	}
}
